// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem1011.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\1011.在-d-天内送达包裹的能力.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-04-26 11:27:54
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-04-26 20:23:30
 */
/*
 * @lc app=leetcode.cn id=1011 lang=cpp
 *
 * [1011] 在 D 天内送达包裹的能力
 */

// @lc code=start
class Solution {
public:
    /**
     * @brief: 当运载能力为mid时，是否再D天内运完
     * @return {*}
     * @note: 
     */
    bool check(vector<int>& weights,int mid, int D)
    {
        int cnt = 1;                // 记录天数
        int cur = 0;                // 记录货物数
        for(auto weight : weights)
        {
            if(mid < weight)        // 船的载运能力低于一个货物的重量
                return false;
            if(cur + weight > mid)
            {
                cnt++;
                cur = 0;
            }
            cur += weight;
        }
        return cnt <= D;
    }



    // 其实就是求最合适的每天的运载能力
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0;
        int right =  50000*50;
        int ans = right;
        while(left < right)
        {
            int mid = (right - left)/2 + left;
            if(check(weights,mid,D))
            {
                right = mid - 1;
                ans = mid;
            }else
            {
                left = mid + 1;
            }
        }
        return ans;
    }   
};
// @lc code=end

